#include <stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

int curr = 0;

// 删除第 n 个节点，并返回删除节点后的链表的头节点
struct ListNode* removeElements(struct ListNode *head, int n) {
    // 最小子问题
    if (head == NULL) return NULL;
    curr++;
    if (curr == n) {
        return head->next;
    }
    struct ListNode *ret = removeElements(head->next, n);
    head->next = ret;
    return head;
}

// 删除倒数第 n 个节点，并返回删除节点后的链表的头节点
struct ListNode* removeNthFromEnd(struct ListNode *head, int n) {
    // 最小子问题
    if (head == NULL) return NULL;

    struct ListNode *ret = removeElements(head->next, n);
    head->next = ret;

    curr++;
    if (curr == n) {
        return head->next;
    }

    return head;
}

// 递归
void printList(struct ListNode *head) {
    if (head == NULL) return;
    printf("%d\n", head->val);
    printList(head->next);
}

int main(void) {
    struct ListNode node2 = {3, NULL};
    struct ListNode node1 = {2, &node2};
    struct ListNode head = {1, &node1};
    printList(removeNthFromEnd(&head, 3));
    return 0;
}
